|
In computer science depth-limited search is an algorithm to explore the vertices of a graph. It is a modification of depth-first search and is used for example in the iterative deepening depth-first search algorithm. == General == Like the normal depth-first search, depth-limited search is an uninformed search. It works exactly like depth-first search, but avoids its drawbacks regarding completeness by imposing a maximum limit on the depth of the search. Even if the search could still expand a vertex beyond that depth, it will not do so and thereby it will not follow infinitely deep paths or get stuck in cycles. Therefore depth-limited search will find a solution if it is within the depth limit, which guarantees at least completeness on all graphs. == Algorithm (informal) == # Determine the vertex where the search should start and assign the maximum search depth # Check if the current vertex is the goal state # * If not: Do nothing # * If yes: return # Check if the current vertex is within the maximum search depth # * If not: Do nothing # * If yes: # *# Expand the vertex and save all of its successors in a stack # *# Call DLS recursively for all vertices of the stack and go back to Step 2 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Depth-limited search」の詳細全文を読む スポンサード リンク
|